//给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
//
// 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
//
//
//
// 示例 1：
//
//
//输入: s1 = "ab" s2 = "eidbaooo"
//输出: True
//解释: s2 包含 s1 的排列之一 ("ba").
//
//
// 示例 2：
//
//
//输入: s1= "ab" s2 = "eidboaoo"
//输出: False
//
//
//
//
// 提示：
//
//
// 1 <= s1.length, s2.length <= 10⁴
// s1 和 s2 仅包含小写字母
//
//
//
//
//
// 注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/
//
// Related Topics 哈希表 双指针 字符串 滑动窗口 👍 94 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 暴力超时
function checkInclusion(s1: string, s2: string): boolean {

    //? 实际上就是在s2中找到连续的s1所有字符

    //? hash就是记录s1 再在s2比较

    let hash = s1.split('')
    let count = 0
    let left = 0
    let right = 0
    while (right < s2.length && left < s2.length - s1.length + 1) {
        let arr = hash.slice()
        count = 0
        while (right < s2.length && arr.includes(s2[right])) {
            arr[arr.indexOf(s2[right])] = '0'
            count++
            if (count === s1.length) return true
            right++
        }
        left++
        right = left
    }
    return false
};
//leetcode submit region end(Prohibit modification and deletion)

//leetcode submit region begin(Prohibit modification and deletion)
function checkInclusion2(s1: string, s2: string): boolean {

    /*
    ? 使用长度为26的数组记录s1中的字母出现次数，在对应位置+1
    ? 使用长度与s1相等的滑动窗口在s2中判断子字符串是否为变位词，方法是在对应位置-1，判断数组是否全为0；
    ? 窗口向前滑动，头部移除的字母重新+1，新加入的字母-1，再次判断。
    ? 当数组所有均为0时说明可以。
     */
    if (s2.length < s1.length) return false
    let counts = new Array(26).fill(0)
    //? 初始 固定窗口长度 也顺便进行了前s1.length的符合性
    for (let i = 0; i < s1.length; i++) {
        counts[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;
        counts[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;
    }
    //? 全0判断
    function areAllZero(counts) {
        for (let i = 0;i < 26;i++) {
            if (counts[i] !== 0) return false;
        }
        return true;
    }
    //? 说明两个字符长度相同且字符相同
    if (areAllZero(counts)) {
        return true;
    }
    //? 保持窗口长度为s1的长度
    for (let i = s1.length; i < s2.length; i++) {
        //? 新加入的字母-1
        counts[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;
        //? 头部移除的字母重新+1
        counts[s2.charCodeAt(i - s1.length) - 'a'.charCodeAt(0)]++;
        if (areAllZero(counts)) {
            return true;
        }
    }
    return false;

};
//leetcode submit region end(Prohibit modification and deletion)
